449B - Jzzhu and Cities - CodeForces Solution

#include "bits/stdc++.h"
#pragma GCC optimize "trapv"
using namespace std ;

const long double EPS = 1e-9 ;
const int MOD=1e9+7 ;
const int N = 4e5 + 5  ;
const int SZ = 2e5 ;
const long long inf = 2e15 ;

#define GOMO_GOMO_NOO ios_base::sync_with_stdio(0),cin.tie(0) , cout.tie(0) ;
#define ll long long
#define endl '\n'
#define all(v) v.begin() , v.end()
int ans = 0 ;
ll dis[N] ;

int main() {

    GOMO_GOMO_NOO
    int n , m , k ;
    cin >> n >> m >> k ;
    vector<vector<pair<int , pair<int , bool >>>> country(n + 1 ) ;
    vector<bool> close(n + 1 , 0 ) ;
    for (int u , v , w , i = 0; i < m ; ++i) {
        cin >> u >> v >> w ;
        country[u].push_back({v , {w , 0 } }) ;
        country[v].push_back({u , {w , 0 } }) ;
    }
    vector<int> train ;
    for (int i = 0; i < k; ++i) {
        int x , y ;
        cin >> x >> y ;
        train.push_back(x) ;
        country[1].push_back({x , {y , 1 }}) ;
        country[x].push_back({1 , {y , 1 }}) ;
    }

    fill(dis , dis + N , inf) ;
    set<pair<ll , pair<int , bool >>> st ;
    st.insert({0 , {1 , 0} }) ;
    dis[1] = 0 ;
    while (!st.empty()){
        ll cost = st.begin()->first ;
        int node = st.begin()->second.first ;

        st.erase(st.begin()) ;
        if(cost > dis[node]){
            continue;
        }
        for(auto i : country[node]){
            ll total_cost = cost + i.second.first ;
            int used = i.second.second ;
            if(total_cost < dis[i.first]){
                dis[i.first] = total_cost ;
                st.insert({total_cost , {i.first , i.second.second }}) ;
                close[i.first] = i.second.second ;
            }else if(!used && dis[i.first] == total_cost){
                close[i.first] = 0 ;
            }
        }
    }
    int cnt = count(all(close) , 1 ) ;
    cout << k - cnt << endl ;
}